﻿namespace Graph;

public class DFSConnectComponet
{
    private IGraph G;
    private bool[] visited;

    public int ComponentCount { get; }

    public DFSConnectComponet(IGraph G)
    {
        this.G = G;
        visited = new bool[G.V];

        for (int v = 0; v < G.V; v++)
        {
            if (!visited[v])
            {
                DFS(v);
                ComponentCount++;
            }
        }
    }

    private void DFS(int v)
    {
        visited[v] = true;

        foreach (int w in G.Adj(v))
        {
            if (!visited[w])
            {
                DFS(w);
            }
        }
    }

    //验证
    static void Main(string[] args)
    {
        IGraph graph = new AdjLinkList("图的深度优先遍历/g.txt");        
        DFSConnectComponet connectComponet = new(graph);      
        Console.WriteLine(connectComponet.ComponentCount);     

        Console.Read();
    }
}
